/***********************************************************************
 ** Reykjavik University
 ** Grímur Tómasson & Eiríkur Fannar Torfason
 ** Copyright (c) 2011. All rights reserved.
 **
 ** This is an implementation of an iterative-deepening, alpha/beta 
 ** pruned MiniMax search. It lends itself well to time-bounded search
 ** scenarios (go deeper and deeper until the time limit is hit).
 **
 **********************************************************************/

#include "IterativeDeepeningAlphaBetaSearch.h"

#include <limits.h>
#include <iostream>

#include "Common.h"
#include "Utility.h"

//----------------------------------------------------------------------------------------------------------
//Declarations
int iterativeDeepeningAlphaBetaSearch_( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int& abort );
int maxValueID( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int alpha, int beta, int& abort );
int minValueID( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int alpha, int beta, int& abort );

//----------------------------------------------------------------------------------------------------------

void* iterativeDeepeningAlphaBetaSearch( void* idAlphaBetaParameters )
{
	IDAlphaBetaParameters* parameters = (IDAlphaBetaParameters*) idAlphaBetaParameters;
	//
	// Let's take stock of the current time so that we can later calculate the elapsed time
	//
	double millisecondsStart = getCurrTimeInMilliseconds();
	//
	// Declare (and initialize) variables
	//
	int bestMove = -1;
	int maxDepth;
	//
	// Iterate, increasing the depth in each iteration of the loop 
	//
	for( maxDepth = 0; maxDepth <= parameters->depthLimit_; ++maxDepth )
	{
		//
		// Find the best move using the current depth limit
		//
		bestMove = iterativeDeepeningAlphaBetaSearch_( parameters->bitboardArray_, 
													   &parameters->currentPly_, 
													  maxDepth, 
													  parameters->expanded_,
													  parameters->abort_ );
		//
		// Update the elapsed time
		//
		double currentMilliseconds = getCurrTimeInMilliseconds();
		parameters->milliseconds_ += currentMilliseconds - millisecondsStart;
		millisecondsStart = currentMilliseconds;
		//
		// This has to be set iteratively since we don't know if we get to finish the next iteration
		//
		parameters->depthReached_ = maxDepth;
		parameters->bestMove_ = bestMove;
		
		//DEBUG
		/*
		std::cout << "Best move for depth " << maxDepth << ": " << bestMove << std::endl;
		std::cout << "Time so far: " << parameters->milliseconds_ << std::endl;
		flush( std::cout );  //DEBUG
		*/
	}
	return 0;  //Null should not be used
}
//----------------------------------------------------------------------------------------------------------

int iterativeDeepeningAlphaBetaSearch_( bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int& abort )
{
	//
	// Declare (and initialize) variables
	//
	int bestMove = -1;
	int bestMoveValue = INT_MIN;
	int value = 0;
	bitboard newBoard;
	//
	// Here we figure out which side is playing. We do this by looking at the current turn number. If it's an even
	// number then it's black's turn (side == 0), otherwise it's red's turn (side == 1). I guess we could use the
	// modulus operator but bitwise operators are simply more bad-ass.
	//
	int side = (*currentPlyPointer)&1;
	//
	// Iterate through the columns (possible moves)
	//
	for( int column = 0; column < WIDTH; ++column )
	{
		//
		// Let's generate a new board where we place a token in the current column
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], column );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(column);
		//
		// Now it's the min-player's turn
		//
		value = minValueID( bitboardArrayPointer, currentPlyPointer, depthLimit, expanded, INT_MIN, INT_MAX, abort );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
//		std::cout << "\tcolumn: " << column << " Score: " << value << std::endl;
		//
		// Is this the best move yet?
		//
		if (value >= bestMoveValue)
		{
			bestMoveValue = value;
			bestMove = column;
		}
	}
	//
	// Return the best move (column) we found
	//
	return bestMove;	
}
//----------------------------------------------------------------------------------------------------------

int maxValueID(  bitboard* bitboardArrayPointer[], int* currentPlyPointer, int depthLimit, int& expanded, int alpha, int beta, int& abort )
{
	//
	// The abort logic for the search thread
	//
	if( abort )  
	{
//		std::cerr << "Aborting search thread!!!  Time: " << getCurrTimeInMilliseconds() << "\n";
		pthread_exit( 0 );
	}
	//
	// Use the turn count (ply) to figure out which color/board Max has and which color Min has
	//
	int side = (*currentPlyPointer)&1;
	int otherSide = side^1;
	//
	// Did the min-player win with the last move?
	//
	if( isLegalHasWon( *bitboardArrayPointer[otherSide] ) )
	{
		//
		// No point in going any further. Return the LOSS value.
		//
		return INT_MIN;
	}
	//
	// Have we reached the depth limit?
	//
	if( !depthLimit )
	{
		//
		// Evaluate the current board and return the value (score)
		//
		return utility( bitboardArrayPointer, currentPlyPointer, side );
	}
	//
	// Increment the number of expanded nodes/states
	//
	++expanded;
	//
	// Declare and initialize variables
	//
	int v = INT_MIN;
	bitboard newBoard;
	//
	// Iterate through the columns (possible moves)
	//
	for( int column = 0; column < WIDTH; ++column )
	{
		//
		// Let's generate a new board where we place a token in the current column
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], column );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(column);
		//
		// Now it's the min-player's turn
		//
		v = max( v, minValueID( bitboardArrayPointer, currentPlyPointer, depthLimit-1, expanded, alpha, beta, abort ) );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
		//
		// Beta-pruning
		//
		if( v >= beta )
		{
			return v;
		}
		//
		// Update the alpha value
		//
		alpha = max( alpha, v );
	}
	//
	// Return the value of Max's best move
	//
	return v;
}
//----------------------------------------------------------------------------------------------------------

int minValueID(  bitboard* bitboardArrayPointer[], int* currentPlyPointer,int depthLimit, int& expanded, int alpha, int beta, int& abort )
{	
	//
	// Use the turn count (ply) to figure out which color Max has and which color Min has
	//
	int side = (*currentPlyPointer)&1;
	int otherSide = side^1;
	//
	// Did the max-player win with the last move?
	//
	if( isLegalHasWon( *bitboardArrayPointer[otherSide] ) )
	{
		//
		// No point in going any further. Return the WIN value.
		//
		return INT_MAX;
	}
	//
	// Have we reached the depth limit?
	//
	if( !depthLimit )
	{
		//
		// Evaluate the current board and return the value (score)
		//
		return utility( bitboardArrayPointer, currentPlyPointer,  side ); 
	}
	//
	// Increment the number of expanded nodes/states
	//
	++expanded;
	//
	// Declare and initialize variables
	//
	int v = INT_MAX;
	bitboard newBoard;
	//
	// Iterate through the columns (possible moves)
	//
	for( int column = 0; column < WIDTH; ++column )  //Possible moves
	{
		//
		// Let's generate a new board where we place a token in the current column
		//
		newBoard = newBoardAndMove( *bitboardArrayPointer[side], column );
		//
		// Was this a legal move or was the column full already?
		//
		if( !isLegal( newBoard ) )
		{
			//
			// We can't place a token in this column. Move on to the next column.
			//
			continue;
		}
		//
		// The move is legal. Let's make the move on the actual board.
		//
		makeMove(column);
		//
		// Now it's the max-player's turn
		//
		v = min( v, maxValueID( bitboardArrayPointer, currentPlyPointer, depthLimit-1, expanded, alpha, beta, abort ) );
		//
		// Backtrack, take back the move we just played.
		//
		undoMove();
		//
		// Alpha-pruning
		//
		if( v <= alpha )
		{
			return v;
		}
		//
		// Update the beta value
		//
		beta = min( beta, v );
	}
	//
	// Return the value of Min's best move
	//
	return v;	
}
//----------------------------------------------------------------------------------------------------------
